Many processes for handling, processing, and manufacturing discrete products consist of a series (or set) of sequential process operations (or subsystems) which are de-coupled by means of in-process storage buffers. Such a process, along with its operating rules, is referred to herein as a buffered industrial process (BIP). For example, a commercial bottling operation represents such a process, while the manufacture of such things as computer chips represents yet another example of a buffered industrial manufacturing system. Non-manufacturing systems may include such systems as mail sorting and handling, high speed systems for inventory selection and movement, and the like. In addition, subsystems within the overall system may contain one or more parallel production facilities, or xe2x80x9clanes,xe2x80x9d which perform an identical function.
FIG. 1 illustrates a typical BIP having mxe2x89xa72 subsystems 12, 14, 16 and mxe2x88x921 buffers 18, 22, 24 in which the ith subsystem has nixe2x89xa71 lanes. Note that each pair of subsystems is separated by a single buffer (e.g., buffer 18) that accepts the combined output of all the lanes supplying it and distributes its products to all the lanes that it supplies, i.e., a xe2x80x9ccommon buffer,xe2x80x9d as used herein.
The design of a BIP is described by its configuration and operating rules. xe2x80x9cConfigurationxe2x80x9d means the number of lane and buffer subsystems, the number of lanes in each manufacturing subsystem, whether or not the lanes are coupled within a given subsystem, and the buffer capacities. For each subsystem, the lanes have specified failure time (xe2x80x9cuptimexe2x80x9d) distributions relative to particular lane speeds and repair time (xe2x80x9cdowntimexe2x80x9d) distributions. Also, lane failure times can be represented as being either xe2x80x9cgood-as-newxe2x80x9d (i.e., failure times reset on a lane failure) or xe2x80x9cgood-as-oldxe2x80x9d (i.e., failure times accumulate after lane failure). For purposes of the discussion, it will be assumed that buffers cannot fail, although buffer failures can be accommodated.
Other lane boundary conditions include the xe2x80x9cmaximum speedxe2x80x9d at which a given lane can be operated, the xe2x80x9cprobability of a false lane restartxe2x80x9d (i.e., the probability of a loss event that occurs quickly relative to the expected life of the system), and the xe2x80x9ctime required for a successful restart.xe2x80x9d A corresponding buffer boundary condition is the xe2x80x9cstarting quantity in the buffer.xe2x80x9d Suppose xe2x80x9cminutesxe2x80x9d are the desired time units of interest. Then a BIP also has a required xe2x80x9cproduction limit specificationxe2x80x9d expressed as the maximum number of products that can be made or handled by the process per minute.
The operating rules for a BIP refer to the xe2x80x9cbuffer trigger levels,xe2x80x9d xe2x80x9clane speedsxe2x80x9d and xe2x80x9clane rules.xe2x80x9d xe2x80x9cLane rulesxe2x80x9d are the rules for operating the lanes within a given subsystem; for example, whether or not lanes can be repaired on the fly (i.e., remaining lanes continue to operate after a lane failure and during repair), a repaired lane can be restarted on the fly, or the lanes must wait for a common restart after all lanes have stopped.
The xe2x80x9cavailabilityxe2x80x9d of a BIP is a product-based availability defined here as the proportion of the number of products made or handled in a specified period of time relative to the potential number of products that could have been made or handled if the process had run without any lane failures during this period. An important problem is how to find configuration and operating rules (that is, BIP designs) that yield high product-based availability. The present invention is directed to this problem. In accordance with our invention, a discrete-event simulation determines the availability of a given BIP design and a genetic algorithm (GA) mutates those BIP designs having high availability until further genetic improvements cease.
The use of a GA to optimize the reliability of a system has been considered by many authors. Gen and Kim (1999) [3] present an excellent state-of-the-art survey on the use of GA-based approaches for various reliability design problems. Coit and Smith (1996) [1] use a GA to optimize the reliability of a series-parallel system. Coit and Smith (1997) [2] discuss a GA to optimize a series-parallel system in which risk profiles of both designer and user are explicitly considered. Painton and Campbell 10 (1995) [13] and Levitin and Lisnianski (1999) [10] also use a GA to optimize the reliability of a series-parallel system. Kumar, Pathak and Gupta (1995) [8] use a GA to optimize the reliability of a computer-network expansion model, while Gen and Cheng (1996) [4] use a GA to optimize the reliability of a redundant system at the subsystem level. Likewise, Ramachandran, Sivakumar and Sathiyanarayanan (1996) [14] take a genetics-based approach to redundancy optimization. While there are many real-world applications of GAs in reliability, several interesting real-world reliability applications in nuclear power plant and power system design are considered in Levitin and Lisnianski (1998) [9] and Levitin and Lisnianski (1999) [11]. However, a GA has not been used to optimize the product-based availability of a complex system, such as a BIP in accordance with our invention.
[1]D. W. Coit, A. E. Smith, xe2x80x9cReliability optimization of series-parallel systems using a genetic algorithmxe2x80x9d, IEEE Trans. Reliability, vol 45, June 1996, pp 254-260.
[2]D. W. Coit, A. E. Smith, xe2x80x9cConsidering risk profiles in design optimization for series-parallel systemsxe2x80x9d, 1997 Proc. Annual Reliability and Maintainability Symposium, 1997, pp 271-277.
[3]M. Gen, J. R. Kim, xe2x80x9cGA-based reliability design: state-of-the-art surveyxe2x80x9d, Computers and Ind. Eng., vol 37, 1999, pp 151-155.
[4]M. Gen, R. Cheng, xe2x80x9cOptimal design of system reliability using interval programming and genetic algorithmsxe2x80x9d, Computers and Ind. Eng., vol 31, 1996, pp 151-155.
[5]D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, 1989; Addison-Wesley.
[6]N. L. Johnson, S. Kotz, Distributions in Statistics: Continuous Univariate Distributionsxe2x80x94January 1970; John Wiley.
[7]N. L. Johnson, S. Kotz, Distributions in Statistics: Continuous Multivariate Distributions, 1972; John Wiley.
[8]A. Kumar, R. M. Pathak, Y. P. Gupta, xe2x80x9cGenetic-algorithm-based reliability optimization for computer network expansionxe2x80x9d, IEEE Trans. Reliability, vol 44, March 1995, pp 63-72.
[9]G. Levitin, A. Lisnianski, xe2x80x9cStructure optimization of power system with bridge topologyxe2x80x9d, Elec. Power Sys. Res., vol 45, 1998, pp 201-208.
[10] G. Levitin, A. Lisnianski, xe2x80x9cJoint redundancy and maintenance optimization for multistate series-parallel systemsxe2x80x9d, Rel. Eng. and Sys. Safety, vol 64, 1999, pp 33-42.
[11] G. Levitin, A. Lisnianski, xe2x80x9cOptimal multistage modernization of power system subject to reliability and capacity requirementsxe2x80x9d, Elec. Power Sys. Res., vol 50, 1999, pp 183-190.
[12] Z. Michalewicz, Genetic Algorithms+Data Structures=Evolution Programs, 1992; Springer-Verlag.
[13] L. Painton, J. Campbell, xe2x80x9cGenetic algorithms in optimization of system reliabilityxe2x80x9d, IEEE Trans. Reliability, vol 44, June 1995, pp 172-178.
[14] V. Ramachandran, V. Sivakumar, K. Sathiyanarayanan, xe2x80x9cGenetics based redundancy optimizationxe2x80x9d, Microelectron. Reliab., vol 37, 1996, pp 661-663.
[15] J. E. Yang, M. J. Hwang, T. Y. Sung, Y. Jin, xe2x80x9cApplication of genetic algorithm for reliability allocation in nuclear power plantsxe2x80x9d, Rel. Eng. and Sys. Safety, vol 65, 1999, pp 229-238.
Various objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
The present invention includes a computer-implemented process for determining optimum configuration parameters for a buffered industrial process. A population is initialized by randomly selecting a first set of design and operation values associated with subsystems and buffers of the buffered industrial process to form a set of operating parameters for each member of the population. An availability discrete event simulation (ADES) is performed on each member of the population to determine the product-based availability of each member. A new population is formed having members with a second set of design and operation values related to the first set of design and operation values through a genetic algorithm and the product-based availability determined by the ADES. Subsequent population members are then determined by iterating the genetic algorithm with product-based availability determined by ADES to form improved sets of design and operation values from which the configuration parameters are selected for the buffered industrial process.